package william.list;

/**
 * @author ZhangShenao
 * @date 2024/3/13
 * @description <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode19_删除链表倒数第N个节点 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 采用快慢指针法,并借助哑头节点
     * 快、慢指针初始情况下都在哑头节点处
     * 快指针先开始向前移动n个节点
     * 然后快、慢指针同时开始向前移动
     * 直到快指针到达链表的尾节点,此时慢指针指向待删除节点的前继节点
     * 直接将待删除节点删除即可
     * <p>
     * 时间复杂度O(N) 只遍历一次链表
     * 空间复杂度O(1)
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //边界条件校验
        if (head == null || n < 1) {
            return head;
        }

        //借助哑头节点
        ListNode dummy = new ListNode();
        dummy.next = head;

        //使用快、慢指针,初始情况都在哑头节点
        ListNode fast = dummy;
        ListNode slow = dummy;

        //快指针先向前移动n个节点
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        //然后快、慢指针同时开始向前移动
        //直到快指针到达链表的尾节点,此时慢指针指向待删除节点的前继节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //此时slow指向待删除节点的前继节点,直接将节点删除即可
        slow.next = slow.next.next;

        //返回头结点
        return dummy.next;
    }
}
